Next, we will have a look at how tiling automata can be combined with restarting technology known from one-dimensional automata~\cite{otto2006restarting}. 

This type of tiling automata does not need such a restricted definition of scanning strategies as before. Hence, we have to rewind this definition. The definitions of this section are extracted from~\cite{prusa2012restarting}. 

\begin{definition}
	A tuple $v = (c_s, f)$ is called a \emph{scanning strategy}, where $c_s \in \{1, 2, 3, 4\}$ is the top-left, top-right, bottom-right or bottom-left corner of a picture and f is a next-position function. Moreover, the sequence of visited positions  $(i_0, j_0), (i_1, j_1), \dots, \\(i_{(m+1)(n+1)-1}, j_{(m+1)(n+1)-1})$ is a permutation of positions of all tiles of size $(2, 2)$ in the picture $\hat{p}$. 
\end{definition}

With this definition we can define $v_{row} = (1, \mathfrak{s}_{row})$ the row-wise and top to bottom scanning strategy. The difference to the previous definitions is that this scanning strategy is not restricted to only visit positions the contiguous positions of which were already visited. 

\begin{definition}
	A 6-tuple $M = (\Sigma, \Gamma, \Theta_f, \delta, v, \mu)$ is called \emph{two-dimensional restarting tiling automaton} (2RTA), where:
	
	\begin{compactitem}
		\item $\Sigma$ is a finite set of characters, the input alphabet,
		\item $\Gamma$ is a finite working alphabet $(\Sigma \subseteq \Gamma)$,
		\item $\Theta_f \subseteq (\Gamma \cup \Sigma)^{2,2}$ is a set of accepting tiles,
		\item $v = (c_s, f)$ is a scanning strategy,
		\item $\mu: \Gamma \rightarrow \mathbb{N}$ is a weight function and
		\item $\delta \subseteq \{(u \rightarrow v) \mid u, v \in (\Gamma \cup \{\#\})^{2,2}\}$ is a set of rewriting rules, where for each rule $u \rightarrow v$ only a single position of u, containing a symbol $a \in \Gamma$ is changed to some $b \in \Gamma$ such that $\mu(b) < \mu(a)$. 
	\end{compactitem}
\end{definition}

The symbols in $\Gamma \setminus \Sigma$ are auxiliary symbols and are not allowed to be in the input word. 

The automaton works as follows: $M$ scans the picture according to the corresponding scanning strategy. The first position a rewrite rule can be applied at, one of the possible rules is selected and rewrites the current tile. The automaton restarts afterwards and continues to look for a position a rewrite rule can be used at. If the automaton reaches the last position of the scanning strategy and there is no rewrite rule that can be executed, the automaton checks, whether the picture belongs to the local language $LOC(\Theta_f)$ or not. If it belongs to $LOC(\Theta_f)$ the automaton accepts, otherwise it rejects. 

Let $p, q \in \Sigma^{*, *}$ be two pictures and $M$ be a 2RTA. We write $p \vdash_M q$ if $q$ is created from $p$ by one rewrite step of $M$. That means, $M$ scans the picture $p$ until a rule can be applied. $M$ executes one of these rules and restarts afterwards. As usual, the reflexive transitive closure of $\vdash$ is denoted as $\vdash^*$. 

Let $M = (\Sigma, \Gamma, \Theta_f, \delta, v, \mu)$ be a two-dimensional restarting tiling automaton. The language accepted by $M$ is \[L(M) = \{p \in \Sigma^{**} \mid \exists q \in \Gamma^{**}: p \vdash_M^* q \text{ and } q \in L(\Theta_f)\}\] 

\begin{definition}
	Let $M = (\Sigma, \Gamma, \Theta_f, \delta, v, \mu)$ be a 2RTA. If for each rule $(u \rightarrow v) \in \delta$ there does not exist a rule $(u \rightarrow v')$ with $v' \not= v$, M is a deterministic two-dimensional restarting tiling automaton (2DRTA). 
\end{definition}

The class of languages accepted by 2RTA's with scanning strategy $v$ is denoted as $\familyOf{v-2RTA}$. 

To point out the method of operation we will reflect an example automaton which only accepts square words of a's. 

\begin{example}
	Let $M = (\Sigma, \Gamma, \Theta_f, \delta, v, \mu)$ be an 2RTA with the input alphabet $\Sigma = \{a\}$, the working alphabet $\Gamma = \{a, 1\}$. The set of tiles $\Theta_f$ is similar to the tiles in Example~\ref{example:local_language}, except that it allows only pictures of a's with 1's on the diagonal. The set of rewrite rules contains the two rules \(\delta = \left\{\begin{tabular}{|c|c|}
					\hline
					\# & \# \\
					\hline
					\# & a \\
					\hline					
				\end{tabular} \rightarrow \begin{tabular}{|c|c|}
					\hline
					\# & \# \\
					\hline
					\# & 1 \\
					\hline					
				\end{tabular}, \begin{tabular}{|c|c|}
					\hline
					1 & a \\
					\hline
					a & a \\
					\hline					
				\end{tabular} \rightarrow \begin{tabular}{|c|c|}
					\hline
					1 & a \\
					\hline
					a & 1 \\
					\hline					
				\end{tabular}\right\}\), $v$ is an arbitrary scanning strategy starting in the top-left corner and $\mu(a) = 2$, $\mu(1) = 1$. 
\end{example}

Let us assume the scanning strategy would be $v_{row}$. The automaton would start at the top-left corner and can apply the first rewrite rule immediately and restarts afterwards. The next rule that can be applied is the second one after the automaton scanned the first row and is at the second column and second row. This can be done, until the left or bottom border of the picture has been reached. If only one of the borders was reached, the picture is not square shaped and does not belong to the local language $LOC(\Theta_f)$. Otherwise, the picture consists of a's and contains 1's on the diagonal. Thus, it belongs to the local language. 

\begin{theorem}
	For each scanning strategy v, $\familyOf{v-2RTA}$ is closed under projection. 
\end{theorem}

\begin{proof}
	Let $\varphi: \Sigma_1 \rightarrow \Sigma_2$ be a projection. We want to show, that if $L_1 \subseteq \Sigma_1$ can be accepted by a $v-2RTA$, then $L_2 = \varphi(L_1)$ is also accepted by an $v-2RTA$. The idea is to use rewrite rules to ``reverse'' the projection and simulate the automaton which works over $\Sigma_1$. The detailed proof can be found in~\cite{prusa2012restarting}. 
\end{proof}

\begin{theorem}
	For any scanning strategy $v$, $\familyOf{v-2RTA}$ is closed under union and intersection. 
\end{theorem}

\begin{proof}
	Both parts of the theorem can be proved with the same strategy. In both cases, we have two restarting tiling automata $M_1$ and $M_2$ and we want to construct an automaton $M$ accepting the union or intersection. At first, the automaton $M$ replaces any symbol $x$ of the input picture by a tuple $(x, x)$. Afterwards, $M_1$ is simulated on the first element in the tuples and $M_2$ is simulated on the second element in the tuples. At last, it must be checked, if the picture belongs to the combination of the local languages (depending on union or intersection). A detailed proof can be found in~\cite{prusa2012new}. 
\end{proof}

If we look at the above example, we see that the definition of a specific scanning strategy seems to be unnecessary. We now want to have a look at what happens if these two-dimensional restarting automata are independent of scanning strategies. Let $L$ be a two-dimensional language. If there exists a $v$-2RTA for any scanning strategy that can accept the language $L$, $L$ is called \emph{strategy independent}. The class of languages containing all strategy independent languages is denoted as si-2RTA. This can be similarly done for 2DRTA and that class is denoted as si-2DRTA. 

Now we have the following corollary: 

\begin{corollary}
	si-2RTL and si-2DRTL are closed under projection, union and intersection. 
\end{corollary}

By rotating or mirroring rules and also applying this operation to the scanning strategy, the following theorem can be proved~\cite{prusa2012restarting}. 

\begin{theorem}
	si-2RTL and si-2DRTL are closed under vertical and horizontal mirroring and rotation. 
\end{theorem}

But we do not know whether si-2RTL is closed under vertical or horizontal concatenations. 

\begin{theorem}
	Let $v$ be a scanning strategy which always ends in the same corner for any picture. Then $\familyOf{v-2DRTA}$ is closed under complement. 
\end{theorem}

It is important that the scanning strategy always ends in the same corner because then the automaton knows when the computation is done. The idea of this proof is to construct an automaton which accepts the complement. This automaton marks any character, whether it belongs to a valid tile or not. If a character belongs to an invalid tile, this marker is spread over the whole picture after the original computation has been done. The local language must only contain tiles with markers of invalid tiles. More in particular can be found in~\cite{prusa2012new}. 

It has been possible to show that REC $\subseteq \familyOf{2RTA}$  and $Diag$-DREC $\subseteq \familyOf{2DRTA}$. 